/*
给定两个数组：
int a[] = {a1,a2,a3,...,an};
int b[] = {b1,b2,b3,...,bn};
给定一个数B
要求：
1. 求出所有满足这个关系 ai + bj <= B的数对（ai,bj）i,j不一定要相等；
2. 复杂度为O(n+k) k为数据对的个数。 
*/

#include "junix.h"
using namespace std;

typedef std::pair<int,int> PAIR;
typedef std::vector<PAIR> VPAIR;
using std::make_pair;
using boost::bind;

void f( int B, int a[], int asz, int b[], int bsz, VPAIR& ret) {
	std::vector<VPAIR> hash_table(B);
	for (int i=0;i<asz;i++) {
		int index = a[i]%B;
		hash_table[index].push_back(make_pair(a[i],i));
	}

	for (int i=0;i<bsz;i++) {
		int index = (B-b[i]%B)%B;
		for (int j=0;j<(int)hash_table[index].size();j++) {
			PAIR& p=hash_table[index][j];
			if ( (b[i]+p.first)==B) {
				ret.push_back(make_pair(p.second,i));
			}
		}
	}
}

int main(int argc, char **argv)
{
	VPAIR ret;
	const int sz = 7000000;
	int B=sz;
	vector<int> a(sz),b(sz);
	srand(time(NULL));
	generate(a.begin(),a.end(),bind(modulus<int>(),bind(rand),sz));
	generate(b.begin(),b.end(),bind(modulus<int>(),bind(rand),sz));

	jtime T;
	T.start();
	f(B,&a[0],sz,&b[0],sz,ret);
	T.end();
	T.print();

	VPAIR::iterator pos = ret.begin();
	for (;pos!=ret.end();++pos) {
		assert(a[pos->first]+b[pos->second] == B);
	/*
		printf("(a[%04d]=%04d,  b[%04d]=%04d)\n",
				pos->first,
				a[pos->first],
				pos->second,
				b[pos->second]);
	*/
	}
}
